package alloy.gui;

import java.util.HashMap;
import java.util.Map;

public class Trie {
    private String prefix;
    private Map subTries;
    private boolean isTerminal;
    private final int commonLength;
    
    public Trie() {
	prefix = null;
	commonLength = 0;
    }
    private Trie(int commonLength_) {
	prefix = null;
	commonLength = commonLength_;
    }
    private Trie(Trie trie, int commonLength_) {
	prefix = trie.prefix;
	subTries = trie.subTries;
	isTerminal = trie.isTerminal;
	commonLength = commonLength_;
    }

    public void add(String s) {
	if (prefix == null) {
	    prefix = s;
	    subTries = null;
	    isTerminal = true;
	    return;
	}

	if (s.equals(prefix)) {
	    isTerminal = true;
	} else if (prefix.startsWith(s)) {
	    Map newSubTries = new HashMap();
	    Character c = new Character(prefix.charAt(s.length()));
	    Trie newTrie = new Trie(this, s.length()+1);
	    newSubTries.put(c, newTrie);

	    prefix = s;
	    subTries = newSubTries;
	    isTerminal = true;
	} else if (s.startsWith(prefix)) {
	    Character c = new Character(s.charAt(prefix.length()));
	    Trie t;

	    if (subTries == null) subTries = new HashMap();
	    if (subTries.containsKey(c)) {
		t = (Trie)subTries.get(c);
	    } else {
		t = new Trie(prefix.length()+1);
		subTries.put(c, t);
	    }
	    t.add(s);
	} else {
	    int i = commonLength;
	    while (s.charAt(i) == prefix.charAt(i)) i++;
	    Map newSubTries = new HashMap();
	    Character c1 = new Character(prefix.charAt(i));
	    Trie t1 = new Trie(this, i+1);
	    newSubTries.put(c1, t1);
	    Character c2 = new Character(s.charAt(i));
	    Trie t2 = new Trie(i+1);
	    t2.add(s);
	    newSubTries.put(c2, t2);

	    prefix = s.substring(0, i);
	    subTries = newSubTries;
	    isTerminal = false;
	}
    }

    // returns null if s not in Trie OR if s has no unique prefix in Trie
    public String minUniquePrefix(String s) {
	if (s.length() < prefix.length()) {
	    return null;
	} else if (s.length() == prefix.length()) {
	    return (isTerminal && (subTries == null)) ?
		prefix.substring(0,commonLength) : null;
	} else {
	    Character c = new Character(s.charAt(prefix.length()));
	    if (subTries.containsKey(c)) {
		return ((Trie)subTries.get(c)).minUniquePrefix(s);
	    } else {
		return null;
	    }
	}
    }
}
